/*
 * @lc app=leetcode.cn id=491 lang=java
 *
 * [491] 非递减子序列
 */

// @lc code=start
import java.util.*;;
class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0);
        return res;
    }

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    private void backtracking(int[] nums, int startIndex) {
        if(path.size() > 1) {
            res.add(new ArrayList<>(path));
        }

        int[] used = new int[201];
        for(int i = startIndex; i < nums.length; i++) {
            if(!path.isEmpty() && nums[i] < path.get(path.size() - 1) || used[nums[i] + 100] == 1) {
                continue;
            }

            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            backtracking(nums, i+1);
            path.remove(path.size() - 1);
        }

    }
}
// @lc code=end

